#include<bits/stdc++.h>
using namespace std;

// string minWindow(string s, string t)
// {
//     unordered_map<char, int> hash;
//     unordered_map<char, int> hash1;
//     string res = "";
//     string temp = "";
//     int len = t.size();
//     for (auto &c : t)
//     {
//         hash[c]++;
//     }
//     int left = 0, right = 0;
//     int count = 0;
//     while (right < s.size())
//     {
//         if (count == len && (res.size() == 0 || res.size() > temp.size()))
//             res = temp;

//         hash1[s[right]]++;
//         temp += s[right];

//         if (hash.count(s[right]) && hash1[s[right]] <= hash[s[right]])
//             count++;
//         while (hash1[s[right]] > hash[s[right]] || hash.count(s[left]) == 0)
//         {
//             hash1[s[left]]--;
//             auto pos = temp.find(s[left]);
//             temp.erase(pos, 1);
//             if (hash.count(s[left]) && hash1[s[left]] < hash[s[left]])
//             {
//                 count--;
//             }
//             if (hash1[s[left]] == 0)
//                 hash1.erase(s[left]);
//             left++;
//         }
//         right++;
//     }
//     if (count == len && (res.size() == 0 || res.size() > temp.size()))
//         res = temp;

//     return res;
// }
// int main()
// {
//     string s = "ADOBECODEBANC", t = "ABC";
//     minWindow(s,t);
// }
 struct ListNode 
 {
      int val;
      ListNode *next;
     ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };


void reorderList(ListNode *head)
{
    ListNode *fast = head;
    ListNode *slow = head;
    ListNode *prev = nullptr;
    while (fast && fast->next) // 找到中间节点猜成两个链表
    {
        prev = slow;
        fast = fast->next->next;
        slow = slow->next;
    }
    prev->next = nullptr;

    ListNode *newhead = new ListNode(-1, nullptr);
    ListNode *cur = slow;
    ListNode *next = nullptr;

    while (cur) // 后半链表逆置
    {
        next = cur->next;
        cur->next = newhead->next;
        newhead->next = cur;
        cur = next;
    }

    // 合并链表
    ListNode *newhead2 = new ListNode(-1);
    cur = newhead2;
    ListNode *list1 = head;
    ListNode *list2 = newhead->next;
    while (list1 && list2)
    {

        cur->next = list1;
        cur = cur->next;
        list1 = list1->next;

        cur->next = list2;
        cur = cur->next;
        list2 = list2->next;

    }

    cur = list1 == nullptr ? list2 : list1;
}

int main()
{
    ListNode* head= new ListNode(0);
    head->val = 1;
    ListNode* head1= new ListNode(0);
    head1->val = 2;
    ListNode* head2= new ListNode(0);
    head2->val = 3;
    ListNode* head3= new ListNode(0);
    head3->val = 4;
    ListNode* head4= new ListNode(0);
    head4->val = 5;

    head->next = head1;
    head1->next = head2;
    head2->next = head3;
    head3->next = head4;
    reorderList(head);

    
}